package easy;

import java.util.ArrayList;
import java.util.List;

/**
 * 163. 缺失的区间
 *
 * 给定一个排序的整数数组 nums ，其中元素的范围在
 * 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。
 *
 * 示例：
 *
 * 输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99,
 * 输出: ["2", "4->49", "51->74", "76->99"]
 *
 * 通过次数10,100提交次数30,469
 */
public class L163_缺失的区间 {
    public static void main(String[] args) {
        System.out.println(new L163_缺失的区间()
                .findMissingRanges(new int[]{-1}, -1, 0));
    }

    /**
     * 执行用时：0 ms, 击败了100.00%的用户
     * 内存消耗：36.6 MB, 击败了74.95%的用户
     */
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        int n = nums.length;

        List<String> res = new ArrayList<>();

        if (nums == null || n == 0){
            helper(lower, upper, res);
            return res;
        }

        if (lower < nums[0]) {
            helper(lower, nums[0] - 1, res);
        }

        int lastNum = nums[0];
        for (int i=1; i<n; i++){
            helper(lastNum + 1, nums[i] -1, res);
            lastNum = nums[i];
        }

        int tmp = nums[n - 1];
        if (tmp < upper) {
            helper(tmp + 1, upper, res);
        }
        return res;

    }

    private void helper(int left, int right, List<String> res){
        if (left > right) return;

        StringBuilder tmp = new StringBuilder();
        if (left == right){
            tmp.append(left);
        } else {
            tmp.append(left).append("->").append(right);
        }

        res.add(tmp.toString());
    }
}
